import java.util.Arrays;

// 尽量减少恶意软件的传播 II
// 给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示
// 在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。
// 一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，
// 且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。
// 这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
// 假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
// 我们可以从 initial 中删除一个节点，
// 并完全移除该节点以及从该节点到任何其他节点的任何连接。
// 请返回移除后能够使 M(initial) 最小化的节点。
// 如果有多个节点满足条件，返回索引 最小的节点 。
// initial 中每个整数都不同
// 测试链接 : https://leetcode.cn/problems/minimize-malware-spread-ii/
public class Code04_MinimizeMalwareSpreadII {

    // 如果测试数据变大，就改变这个值
    public static int MAXN = 301;

    // [3,6,103]
    // virus[3] = true;
    // virus[103] = true;
    // 方便查询
    public static boolean[] virus = new boolean[MAXN];

    // 每个源头点删掉的话，能拯救多少点的数据
    public static int[] cnts = new int[MAXN];

    // 集合的标签 : 集合的感染点是什么点
    // a : 代表点，整个集合源头是 infect[a]
    // infect[a] == -1，目前这个集合没有发现源头
    // infect[a] >= 0，目前这个集合源头是 infect[a]
    // infect[a] == -2，目前这个集合源头不止一个，已经无法拯救了!
    public static int[] infect = new int[MAXN];

    // 并查集固有信息
    public static int[] father = new int[MAXN];

    // 集合的标签 : 集合的大小是多少
    public static int[] size = new int[MAXN];

    // 集合一定只放普通点，源头点根本不参与集合，也不是元素！

    public static void build(int n, int[] initial) {
        for (int i = 0; i < n; i++) {
            virus[i] = false;
            cnts[i] = 0;
            infect[i] = -1;
            size[i] = 1;
            father[i] = i;
        }
        for (int i : initial) {
            virus[i] = true;
        }
    }

    public static int find(int i) {
        if (i != father[i]) {
            father[i] = find(father[i]);
        }
        return father[i];
    }

    public static void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            father[fx] = fy;
            size[fy] += size[fx];
        }
    }

    public static int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        build(n, initial);
        // 不是病毒的点，普通点合并！
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] == 1 && !virus[i] && !virus[j]) {
                    union(i, j);
                }
            }
        }
        // 病毒周围的普通点(集合 )去设置源头！
        for (int sick : initial) {
            for (int neighbor = 0; neighbor < n; neighbor++) {
                if (sick != neighbor && !virus[neighbor] && graph[sick][neighbor] == 1) {
                    int fn = find(neighbor);
                    if (infect[fn] == -1) {
                        infect[fn] = sick;
                    } else if (infect[fn] != -2 && infect[fn] != sick) {
                        infect[fn] = -2;
                    }
                }
            }
        }
        // 统计拯救数据
        for (int i = 0; i < n; i++) {
            // 不是代表点，不看
            if (i == find(i) && infect[i] >= 0) {
                cnts[infect[i]] += size[i];
            }
        }
        Arrays.sort(initial);
        int ans = initial[0];
        int max = cnts[ans];
        for (int i : initial) {
            if (cnts[i] > max) {
                ans = i;
                max = cnts[i];
            }
        }
        return ans;
    }

}